package com.celan.year2023.month01.day05;

import java.util.*;

public class Solution2 {
    public int countPairs(int[] nums, int low, int high) {
        int ans = 0;
        HashMap<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) cnt.put(x, cnt.getOrDefault(x, 0) + 1);
        for (++high; high > 0; high >>= 1, low >>= 1) {
            HashMap<Integer, Integer> nxt = new HashMap<Integer, Integer>();
            for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
                int x = e.getKey(), c = e.getValue();
                ans += c * (high % 2 * cnt.getOrDefault((high - 1) ^ x, 0) -
                        low % 2 * cnt.getOrDefault((low - 1) ^ x, 0));
                nxt.put(x >> 1, nxt.getOrDefault(x >> 1, 0) + c);
            }
            cnt = nxt;
        }
        return ans / 2;
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        Set<String> set = new HashSet<>();
        for (String word : wordDict) {
            set.add(word);
        }
        boolean[] dp = new boolean[n + 10];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i && !dp[i]; j++) {
                if (set.contains(s.substring(j - 1, i))) {
                    dp[i] = dp[j - 1];
                }
            }
        }
        return dp[n];
    }

    public int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE, imax = 1, imin = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) {
                int temp = imax;
                imax = imin;
                imin = temp;
            }
            imax = Math.max(imax * nums[i], nums[i]);
            imin = Math.min(imin * nums[i], nums[i]);
            max = Math.max(max,imax);
        }
        return max;
    }
}
